{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Container With Most Water"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #盛最多水的容器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组&nbsp;<code>height</code>&nbsp;。有&nbsp;<code>n</code>&nbsp;条垂线，第 <code>i</code> 条线的两个端点是&nbsp;<code>(i, 0)</code>&nbsp;和&nbsp;<code>(i, height[i])</code>&nbsp;。</p>\n",
    "\n",
    "<p>找出其中的两条线，使得它们与&nbsp;<code>x</code>&nbsp;轴共同构成的容器可以容纳最多的水。</p>\n",
    "\n",
    "<p>返回容器可以储存的最大水量。</p>\n",
    "\n",
    "<p><strong>说明：</strong>你不能倾斜容器。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,8,6,2,5,4,8,3,7]\n",
    "<strong>输出：</strong>49 \n",
    "<strong>解释：</strong>图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为&nbsp;49。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>height = [1,1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == height.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= height[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [container-with-most-water](https://leetcode.cn/problems/container-with-most-water/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [container-with-most-water](https://leetcode.cn/problems/container-with-most-water/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,8,6,2,5,4,8,3,7]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = len(height) - 1\n",
    "        \n",
    "        max_area = min(height[j], height[i]) * (j - i)\n",
    "        while i < j:\n",
    "            flag = 0\n",
    "            m = height[i]\n",
    "            n = height[j]\n",
    "            if m > n:\n",
    "                for k in range(j, i, -1):\n",
    "                    if height[k] > n:\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag == 1:\n",
    "                    j = k\n",
    "                    max_area = max(min(height[i], height[j]) * (j - i), max_area)\n",
    "                    continue\n",
    "                \n",
    "\n",
    "            elif m <= n:\n",
    "                for k in range(i+1, j):\n",
    "                    if height[k] > m:\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag == 1:\n",
    "                    i = k\n",
    "                    max_area = max(min(height[i], height[j]) * (j - i), max_area)\n",
    "                    continue\n",
    "            \n",
    "            if flag == 0:\n",
    "                break\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        return max_area\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if height is None or len(height) < 2:\n",
    "            return 0\n",
    "\n",
    "        sp = [0]\n",
    "        tmp = height[0]\n",
    "        start = 1\n",
    "        while start < len(height) - 1:\n",
    "            if height[start] > tmp:\n",
    "                tmp = height[start]\n",
    "                sp.append(start)\n",
    "            start += 1\n",
    "\n",
    "        ep = [len(height) - 1]\n",
    "        tmp = height[len(height) - 1]\n",
    "        end = len(height) - 2\n",
    "        while end > 0:\n",
    "            if height[end] > tmp:\n",
    "                tmp = height[end]\n",
    "                ep.append(end)\n",
    "            end -= 1\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(0, len(sp)):\n",
    "            for j in range(0, len(ep)):\n",
    "                if sp[i] < ep[j]:\n",
    "                    tmp = (ep[j] - sp[i]) * min(height[ep[j]], height[sp[i]])\n",
    "                    if tmp > ret:\n",
    "                        ret = tmp\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        left, right = 0, len(height)-1\n",
    "        water = 0\n",
    "        while left <= right:\n",
    "            water = max(water, (right-left)*min(height[left], height[right]))\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return water\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_container = 0\n",
    "        flag = [0] * len(height)\n",
    "        for point in range(len(height)):\n",
    "            if flag[point]: continue\n",
    "            for back in range(len(height) - 1, point, -1):\n",
    "                if flag[back]: continue\n",
    "                if height[back] <= height[point]:\n",
    "                    now_container = (back - point) * height[back]\n",
    "                    max_container = max(now_container, max_container)\n",
    "                    flag[back] = 1\n",
    "                    print(max_container)\n",
    "                    continue\n",
    "                if height[back] >= height[point]:\n",
    "                    now_container = (back - point) * height[point]\n",
    "                    max_container = max(now_container, max_container)\n",
    "                    flag[point] = 1\n",
    "                    print(max_container)\n",
    "                    break\n",
    "\n",
    "        print(max_container)\n",
    "        return max_container"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # time limit exceed\n",
    "        # max_all = 0\n",
    "        # for i in range(len(height)):\n",
    "        #     max_cur = 0\n",
    "        #     if height[i] * (len(height) - i) <= max_all:\n",
    "        #         continue\n",
    "        #     for j in range(i, len(height)):\n",
    "        #         max_all = max(max_all, min(height[i], height[j]) * (j - i))\n",
    "        # return max_all\n",
    "        \n",
    "        # faster two pointers\n",
    "        left = 0\n",
    "        max_area = 0\n",
    "        right = len(height) - 1\n",
    "        while left < right:\n",
    "            max_area = max(max_area, min(height[right], height[left]) * (right - left))\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxArea(self, heights: list) -> int:\n",
    "\t\t'''\n",
    "\t\theights: [h1, h2, h3, ..., hn]\n",
    "\t\tfind (i, j) that\n",
    "\t\tA = (i - j) * max(hi, hj) reaches max value\n",
    "\t\t'''\n",
    "\t\t\n",
    "\t\t'''h_seq = [(i, hi) from max to min]'''\n",
    "\t\t\n",
    "\t\tle = len(heights)\n",
    "\t\th_seq = sorted(enumerate(heights), key = lambda _: _[1])[::-1]\n",
    "\t\tif h_seq[0][0] < h_seq[1][0]:\n",
    "\t\t\tleft, right = h_seq[0][0], h_seq[1][0]\n",
    "\t\telse:\n",
    "\t\t\tleft, right = h_seq[1][0], h_seq[0][0]\n",
    "\t\t\t\n",
    "\t\tre = (right - left) * h_seq[1][1]\n",
    "\t\tpossible_max = h_seq[1][1] * le\n",
    "\t\tpoint = 2\n",
    "\t\t\n",
    "\t\twhile re <= possible_max and point < le:\n",
    "\t\t\tif h_seq[point][0] < left:\n",
    "\t\t\t\tleft = h_seq[point][0]\n",
    "\t\t\telif h_seq[point][0] > right:\n",
    "\t\t\t\tright = h_seq[point][0]\n",
    "\t\t\telse: \n",
    "\t\t\t\tpoint += 1\n",
    "\t\t\t\tcontinue\n",
    "\t\t\tarea = (right - left) * min(heights[left], heights[right])\n",
    "\t\t\tpossible_max = min(heights[left], heights[right]) * le\n",
    "\t\t\tpoint += 1\n",
    "\t\t\tre = area if area > re else re\n",
    "\t\treturn re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left_cand = []\n",
    "        right_cand = []\n",
    "        n = len(height)\n",
    "        left_min = float('-inf')\n",
    "        for i in range(n):\n",
    "            if left_min < height[i]:\n",
    "                left_min = height[i]\n",
    "                left_cand.append((height[i], i))\n",
    "        \n",
    "        right_min = float('-inf')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if right_min < height[i]:\n",
    "                right_min = height[i]\n",
    "                right_cand.append((height[i], i))\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "        max_vol = 0\n",
    "        while i < len(left_cand) and j < len(right_cand):\n",
    "            left_y, left_x = left_cand[i]\n",
    "            right_y, right_x = right_cand[j]\n",
    "            max_vol = max(max_vol, min(right_y, left_y) * (right_x - left_x))\n",
    "            if left_x >= right_x:\n",
    "                break\n",
    "            if left_y < right_y:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return max_vol\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        position = [(x, height[x]) for x in range(len(height))]\n",
    "        positionSort = sorted(position, key=lambda x: x[1], reverse=True)\n",
    "        position = [position for position, height in positionSort]\n",
    "        height = [height for position, height in positionSort]\n",
    "        if position[0] < position[1]:\n",
    "            maxPos, minPos = position[1], position[0]\n",
    "        else:\n",
    "            maxPos, minPos = position[0], position[1]\n",
    "        for i in range(1, len(height)):\n",
    "            maxPos = max(maxPos, position[i])\n",
    "            minPos = min(minPos, position[i])\n",
    "            temp = maxPos - minPos        \n",
    "            res = max(temp*height[i], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\" \n",
    "        length = len(height)\n",
    "        max_area = 0\n",
    "        register = []\n",
    "        for i, h in enumerate(height, 1):\n",
    "            register.append((h, i))\n",
    "        register.sort()\n",
    "        has_seen = []\n",
    "        last = register.pop()\n",
    "        h, w = last\n",
    "        has_seen.append(w)\n",
    " \n",
    "        for r in register[::-1]:\n",
    "            y, x = r\n",
    "            has_seen.append(x)\n",
    "            min_x = min(has_seen)\n",
    "            max_x = max(has_seen)\n",
    "            cur = y * max(x - min_x, max_x - x)\n",
    "            if cur >= max_area:\n",
    "                max_area = cur\n",
    "            print(cur)\n",
    "        return max_area\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: 'List[int]') -> 'int':\n",
    "        len1 = len(height)\n",
    "        b = sorted(enumerate(height), key=lambda x: x[1])\n",
    "        index = []\n",
    "        for o in b:\n",
    "            index.append(o[0])\n",
    "        mymax = 0\n",
    "        for i in range(len1-1):\n",
    "            end = 0\n",
    "            # print('index', index[i])\n",
    "            if index[i] < len1/2:\n",
    "                # print('small', len1-1, 2*index[i])\n",
    "                for j in range(len1-1, 2*index[i], -1):\n",
    "                   # print('height[index[i]] , height[j]', height[index[i]], height[j])\n",
    "                    if height[index[i]] <= height[j]:\n",
    "                        tmpmax = height[index[i]] * (j - index[i])\n",
    "                        # print('tmpmax', tmpmax)\n",
    "                        end = 1\n",
    "                        if tmpmax > mymax:\n",
    "                            mymax = tmpmax\n",
    "                        break\n",
    "                if end==0:\n",
    "                    # beford no found\n",
    "                    for j in range(0, index[i]):\n",
    "                        if height[index[i]] <= height[2 * index[i] - j]:\n",
    "                            tmpmax = height[index[i]] * (2 * index[i] - j - index[i])\n",
    "                            if tmpmax > mymax:\n",
    "                                mymax = tmpmax\n",
    "                            break\n",
    "                        if height[index[i]] <= height[j]:\n",
    "                            tmpmax = height[index[i]] * (index[i]-j)\n",
    "                            if tmpmax > mymax:\n",
    "                                mymax = tmpmax\n",
    "                            break              \n",
    "            else:\n",
    "                print('big', 2 * index[i] - len1 + 1)\n",
    "                for j in range(0, 2 * index[i] - len1 + 1):\n",
    "                    if height[index[i]] <= height[j]:\n",
    "                        tmpmax = height[index[i]] * (index[i] - j)\n",
    "                        end = 1\n",
    "                        if tmpmax > mymax:\n",
    "                            mymax = tmpmax\n",
    "                        break\n",
    "                if end==0:\n",
    "                    # beford no found\n",
    "                    for j in range(0, len1 - 1 - index[i]):\n",
    "                        if height[index[i]] <= height[2 * index[i] - len1 + 1 + j]:\n",
    "                            tmpmax = height[index[i]] * (len1 - 1 - index[i] -j)\n",
    "                            if tmpmax > mymax:\n",
    "                                mymax = tmpmax\n",
    "                            break\n",
    "                        if height[index[i]] <= height[len1 - 1 - j]:\n",
    "                            tmpmax = height[index[i]] * (len1 - 1 - j - index[i])\n",
    "                            if tmpmax > mymax:\n",
    "                                mymax = tmpmax\n",
    "                            break\n",
    "                        \n",
    "        return mymax\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"      \n",
    "        max_area = 0\n",
    "        pairs = []\n",
    "        for i, h in enumerate(height, 1):\n",
    "            pairs.append((h, i))\n",
    "        pairs.sort()\n",
    "        heights = [p[0] for p in pairs]\n",
    "        index = [p[1] for p in pairs]\n",
    "        print(heights)\n",
    "        for ix, pair in enumerate((zip(heights[:-1], index[:-1]))):\n",
    "            h, w = pair\n",
    "            max_x = max(index[ix+1:])\n",
    "            min_x = min(index[ix+1:])\n",
    "            w_ = max(w - min_x, max_x - w)\n",
    "            cur = h * w_\n",
    "            if cur >= max_area:\n",
    "                max_area = cur\n",
    "        \n",
    "        return max_area\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\" \n",
    "        length = len(height)\n",
    "        max_area = 0\n",
    "        register = []\n",
    "        for i, h in enumerate(height, 1):\n",
    "            register.append((h, i))\n",
    "        register.sort()\n",
    "        has_seen = set()\n",
    "        last = register.pop()\n",
    "        h, w = last\n",
    "        has_seen.add(w)\n",
    "        count = 0\n",
    "        for r in register[::-1]:\n",
    "            count += 1\n",
    "            y, x = r\n",
    "            has_seen.add(x)\n",
    "            min_x = min(has_seen)\n",
    "            max_x = max(has_seen)\n",
    "            x_ =  max(x - min_x, max_x - x)\n",
    "            cur = y * x_\n",
    "            if cur >= max_area:\n",
    "                max_area = cur\n",
    "            if count >= 2/3 * length:\n",
    "                break\n",
    "        return max_area\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        h=height\n",
    "        mh=max(h)\n",
    "        a=0\n",
    "        l=[]\n",
    "        for i in range(h.index(mh)+1):\n",
    "            if h[i]>a:\n",
    "                a=h[i]\n",
    "                l.append([h[i],i])\n",
    "        print(l,'---l')\n",
    "        a=0\n",
    "        ll=len(l)\n",
    "        \n",
    "        for i in range(len(h)-1,-1,-1):\n",
    "            if h[i]==mh:\n",
    "                l.insert(ll,[h[i],i])\n",
    "                break\n",
    "            else:\n",
    "                if h[i]>a:\n",
    "                    a=h[i]\n",
    "                    l.insert(ll,[h[i],i])\n",
    "        print(l,'---l')\n",
    "        j=l[-1]\n",
    "        res=0\n",
    "        for i in l:\n",
    "            if i[1]>j[1]:\n",
    "                break\n",
    "            for j in l[-1::-1]:\n",
    "                if i[0]>j[0]:\n",
    "                    res=max(j[0]*(j[1]-i[1]),res)\n",
    "                else :\n",
    "                    res=max(i[0]*(j[1]-i[1]),res)\n",
    "                    break\n",
    "        return res\n",
    "            \n",
    "  #       h=height\n",
    "  #       mh=max(h)\n",
    "  #       l=[]\n",
    "  #       a=h[0]\n",
    "  #       for i in range(1,len(h)-1):\n",
    "  #           if max(h[:i])>=h[i] and max(h[i+1:])>=h[i]:\n",
    "  #               h[i]=0\n",
    "  # #      print(h)\n",
    "  #       res=0\n",
    "  #       j=len(h)\n",
    "  #       for i in range(len(h)):\n",
    "  #           if i>j:\n",
    "  #           #    print(i,j)\n",
    "  #               break\n",
    "  #           if h[i]!=0:\n",
    "  #               for j in range(len(h)-1,0,-1):\n",
    "  #                   if i>j:\n",
    "  #             #          print(i,j,'---')\n",
    "  #                       break\n",
    "  #                   if h[j]!=0:\n",
    "  #                       if h[i]>h[j]:\n",
    "  #                           res=max(h[j]*(j-i),res)\n",
    "  #                       if h[i]<=h[j]:\n",
    "  #                           res=max(h[i]*(j-i),res)\n",
    "  #                           break\n",
    "  #       return res\n",
    "                    \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        index = {}\n",
    "        for i, h in enumerate(height):\n",
    "            if h in index.keys():\n",
    "                index[h].append(i)\n",
    "            else:\n",
    "                index[h] = [i]\n",
    "        # index = {h: i for h in enumerate(height)}\n",
    "        dropped = [False] * len(height)\n",
    "        l, r = 0, len(height) - 1\n",
    "        height.sort()\n",
    "        ans = 0\n",
    "        for h in height:\n",
    "            il = index[h]\n",
    "            ans = max(ans, (r - min(il)) * h, ans)\n",
    "            ans = max(ans, (max(il) - l) * h, ans)\n",
    "            for i in il:\n",
    "                dropped[i] =True\n",
    "            while l < r and dropped[l]:\n",
    "                l += 1\n",
    "            while l < r and dropped[r]:\n",
    "                r -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        location_map = {}\n",
    "        length = len(height)\n",
    "        for i in range(length):\n",
    "            if height[i] not in location_map:\n",
    "                location_map[height[i]] = []\n",
    "            location_map[height[i]].append(i)\n",
    "        new_list = sorted(height, reverse=True)\n",
    "        left = location_map[new_list[0]][0]\n",
    "        right = location_map[new_list[0]][0]\n",
    "        max_num = 0\n",
    "        for i in range(length):\n",
    "            for j in range(len(location_map[new_list[i]])):\n",
    "                location = location_map[new_list[i]][j]\n",
    "                if new_list[i] * abs(location - left) > max_num:\n",
    "                    max_num = new_list[i] * abs(location - left)\n",
    "                if new_list[i] * abs(location - right) > max_num:\n",
    "                    max_num = new_list[i] * abs(location - right)\n",
    "                if location < left:\n",
    "                    left = location\n",
    "                if location > right:\n",
    "                    right = location\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: 'List[int]') -> 'int':\n",
    "        left,right,maxarea = 0,len(height)-1,0\n",
    "        while left < right:                     #【错1】while写成if\n",
    "            if height[left] < height[right]:\n",
    "                tmp = (right - left)*height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                tmp = (right - left)*height[right]\n",
    "                right -= 1\n",
    "            maxarea = tmp if tmp > maxarea else maxarea\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        max_are = 0\n",
    "        found_index = True\n",
    "        index_line = 1\n",
    "        while found_index:\n",
    "            left = 0\n",
    "            right = len(height) - 1\n",
    "            index_left = None\n",
    "            index_right = None\n",
    "            remove_index = []\n",
    "            while left < right:\n",
    "                if height[left] >= index_line:\n",
    "                    index_left = left\n",
    "                else:\n",
    "                    remove_index.append(left)\n",
    "                if height[right] >= index_line:\n",
    "                    index_right = right\n",
    "                else:\n",
    "                    remove_index.append(right)\n",
    "                if index_left is not None and index_right is not None:\n",
    "                    break\n",
    "                if index_right is None:\n",
    "                    right = right - 1\n",
    "                if index_left is None:\n",
    "                    left = left + 1\n",
    "            if index_left is None and index_right is None:\n",
    "                found_index = False\n",
    "            max_are = max(max_are, index_line * (right - left))\n",
    "            index_line = index_line + 1\n",
    "\n",
    "            remove_index.sort()\n",
    "            while len(remove_index) > 0:\n",
    "                height.pop(remove_index.pop())\n",
    "        return max_are"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        max_area = 0\n",
    "        while len(height) >= 2:\n",
    "            if height[0] == height[-1]:\n",
    "                line_height = height[0]\n",
    "                area = height[0] * (len(height) - 1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "                height.pop(0)\n",
    "                height.pop()\n",
    "            elif height[0] > height[-1]:\n",
    "                line_height = height[-1]\n",
    "                area = height[-1] * (len(height) - 1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "                height.pop()  \n",
    "            else:\n",
    "                line_height = height[0]\n",
    "                area = height[0] * (len(height) - 1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "                height.pop(0)  \n",
    "        return max_area\n",
    "        \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        num, nums, numl = 0, [height.index(max(height)), height.index(max(height))], sorted(height)\n",
    "        for i in range(len(height)):\n",
    "            x = numl[-1]\n",
    "            numl.pop()\n",
    "            y = height.index(x)\n",
    "            z = max(abs(nums[0] - y), abs(nums[1] - y)) * x\n",
    "            num = max(num, z)\n",
    "            nums.append(y)\n",
    "            nums = [min(nums), max(nums)]\n",
    "            height[y] = 0\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 用numpy矩阵超时\n",
    "# class Solution:\n",
    "#     def maxArea(self, height: List[int]) -> int:\n",
    "#         n = len(height)\n",
    "#         assert n >= 2\n",
    "#         memory = np.zeros((n, n))\n",
    "#         for i in range(1, n + 1):          # i 表示间隔\n",
    "#             for j in range(n - i):         # j 表示横坐标 \n",
    "#             #    0,1 1,2 2,3 3,4 ... n-3,n-2 n-2,n-1\n",
    "#             #      0,2 1,3 2,4 3,5 ...    n-3, n-1\n",
    "#             #         0,3 ...\n",
    "#             #                  ........\n",
    "#             #                    0,n-1        \n",
    "#                 if i == 1:                 # 初始化\n",
    "#                     memory[j, j+i] = min(height[j], height[j+i])\n",
    "#                 else:\n",
    "#                     memory[j, j+i] = max(memory[j, j+i-1], memory[j+1, j+i], i*(min(height[j], height[j+i])))\n",
    "#         return memory[0, n-1]\n",
    "\n",
    "# 用一个list\n",
    "# class Solution:\n",
    "#     def maxArea(self, height: List[int]) -> int:\n",
    "#         n = len(height)\n",
    "#         assert n >= 2\n",
    "#         memory = []\n",
    "#         for j in range(n-1):\n",
    "#             memory.append(min(height[j], height[j+1]))\n",
    "#         for i in range(2, n+1):\n",
    "#             for j in range(n-i):\n",
    "#                 memory[j] = max(memory[j], memory[j+1], i*(min(height[j], height[j+i])))\n",
    "#         return memory[0]\n",
    "\n",
    "# O(n),要使得体积最大，要么底最大，要么最高\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        maxv = (len(height)-1)*min(height[0], height[-1])\n",
    "        i, j = 0, len(height)-1\n",
    "        while i<j:\n",
    "            if height[i] < height[j]: \n",
    "                maxv = max(maxv, (j-i-1)*min(height[i+1], height[j]))\n",
    "                i += 1\n",
    "            else:\n",
    "                maxv = max(maxv, (j-i-1)*min(height[i], height[j-1]))\n",
    "                j -= 1\n",
    "        return maxv\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left, right = 0, n - 1\n",
    "        max_area = min(height[0], height[n - 1]) * (n - 1)\n",
    "\n",
    "        while left <= right:\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "            \n",
    "            max_area = max(max_area,min(height[left], height[right]) * (right - left))\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(height) - 1\n",
    "        max_area = 0\n",
    "\n",
    "        while right != left and left < right:\n",
    "            area = (right - left) * min([height[left], height[right]])\n",
    "            max_area = area if area > max_area else max_area\n",
    "\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return max_area\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        start  = 0\n",
    "        end = len(height)-1\n",
    "        ma = []\n",
    "\n",
    "        while start < end:\n",
    "            num = end - start\n",
    "            if height[start] < height[end]:\n",
    "                m =  min(height[start], height[end]) * num\n",
    "                print(m)\n",
    "                ma.append(m)\n",
    "                start += 1\n",
    "            else:\n",
    "                m =  min(height[start], height[end]) * num\n",
    "                print(m)\n",
    "                ma.append(m)\n",
    "                end -= 1\n",
    "        return max(ma)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        h1=0\n",
    "        h2=len(height)-1\n",
    "        s0 = min(height[h1],height[h2])*(h2-h1)\n",
    "        for i in range(1,len(height)):\n",
    "            if height[h2]>height[h1]:\n",
    "                h1+=1\n",
    "            else:\n",
    "                h2-=1\n",
    "            s = min(height[h1],height[h2])*(h2-h1)\n",
    "            if s>s0:\n",
    "                s0=s\n",
    "        return s0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(height)-1\n",
    "        maxarea = 0\n",
    "        while left < right:\n",
    "            maxarea = max(maxarea, min(height[right], height[left])*(right-left))\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return maxarea\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        maxarea, hidden_height, left, right = 0, 0, 0, len(height)-1\n",
    "        while left != right:\n",
    "            height_left, height_right = height[left], height[right]\n",
    "            if height_left < hidden_height:\n",
    "                left += 1\n",
    "            elif height_right < hidden_height:\n",
    "                right -= 1\n",
    "            else:\n",
    "                if height_left < height_right:\n",
    "                    min_height = height_left\n",
    "                else:\n",
    "                    min_height = height_right\n",
    "                area = (right - left) * min_height\n",
    "                hidden_height = min_height + 1\n",
    "            if area > maxarea:\n",
    "                maxarea = area\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        length = len(height)\n",
    "        s = []\n",
    "        i = 0\n",
    "        j = length - 1\n",
    "        while(i < j):\n",
    "            area = (j - i)*min(height[i],height[j])\n",
    "            s.append(area)\n",
    "            if(height[i] < height[j]):\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        res = []\n",
    "        l = 0\n",
    "        r = len(height)-1\n",
    "        while l < r:\n",
    "            res.append(min(height[l], height[r]) * (r - l))\n",
    "            if height[l] <= height[r]:\n",
    "                l = l + 1\n",
    "                res.append(min(height[l], height[r])*(r-l))\n",
    "            else:\n",
    "                r = r - 1\n",
    "                res.append(min(height[l], height[r]) * (r - l))\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        sorted_nums = sorted(enumerate(height), key=lambda x: x[1])\n",
    "        idx = [i[0] for i in sorted_nums]\n",
    "        Height = [i[1] for i in sorted_nums]\n",
    "        Height_set = sorted(list(set(height)))\n",
    "        i = len(Height_set)-2\n",
    "        max_ = 0\n",
    "        index_ = sorted(idx[Height.index(Height_set[-1]):])\n",
    "        min_idx = index_[0]\n",
    "        max_idx = index_[-1]\n",
    "        Area = (max_idx-min_idx)*Height_set[-1]\n",
    "        last_idx = Height.index(Height_set[-1])\n",
    "        if Area>max_:\n",
    "            max_=Area\n",
    "        while i>=0:\n",
    "            h = Height_set[i]\n",
    "            index_ = idx[Height.index(h):last_idx]\n",
    "            index_ = sorted(index_)\n",
    "            index_ = sorted([index_[-1], index_[0], min_idx, max_idx])\n",
    "            Area = (index_[-1]-index_[0])*h\n",
    "            if Area>max_:\n",
    "                max_=Area\n",
    "            last_idx = Height.index(h)\n",
    "            min_idx = index_[0]\n",
    "            max_idx = index_[-1]\n",
    "            i-=1\n",
    "        \n",
    "        return max_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "\n",
    "        def Cleanup(height: List[int]):\n",
    "\n",
    "            #先去掉不可能是正确答案的线，使输入变成金字塔形\n",
    "            #第一个max之前和最后一个max之后是可能的范围\n",
    "            #valid_input是所有可能成为答案的线的集合，List[tuple]\n",
    "            #tuple[0]表示横坐标，[1]表示纵坐标\n",
    "            first_max = height.index(max(height))\n",
    "            last_max = len(height) - next(i for i, v in enumerate(reversed(height), 1) if v == max(height))\n",
    "            valid_input = []\n",
    "            curr_height = height[0]\n",
    "            \n",
    "            #左半边\n",
    "            for i in range(first_max + 1):\n",
    "                if height[i] >= curr_height:\n",
    "                    valid_input.append((i, height[i]))\n",
    "                    curr_height = height[i]\n",
    "\n",
    "            curr_height = height[-1]\n",
    "            right_side_valid = []\n",
    "            #右半边\n",
    "\n",
    "            for i in range(len(height) - last_max):\n",
    "                if height[-i - 1] >= curr_height:\n",
    "                    right_side_valid.append((len(height) -i - 1, height[-i - 1]))\n",
    "                    curr_height = height[-i - 1]\n",
    "            \n",
    "            right_side_valid.reverse()\n",
    "\n",
    "            valid_input += right_side_valid\n",
    "            \n",
    "            # print(valid_input)\n",
    "            return valid_input\n",
    "\n",
    "        def getSolution(valid_input: List[tuple]) -> int:\n",
    "            #两个out之间的体积和两个in之间进行比对，输的那一方中短的那条线肯定不是正确答案，移除掉\n",
    "            out_left = 0\n",
    "            out_right = len(valid_input) - 1\n",
    "            in_left = out_left + 1\n",
    "            in_right = out_right - 1\n",
    "            max_vol = 0\n",
    "\n",
    "            while in_left < in_right:\n",
    "                out_vol = (valid_input[out_right][0] - valid_input[out_left][0]) * min(valid_input[out_left][1], valid_input[out_right][1])\n",
    "                in_vol = (valid_input[in_right][0] - valid_input[in_left][0]) * min(valid_input[in_left][1], valid_input[in_right][1])\n",
    "                left_vol = (valid_input[in_right][0] - valid_input[out_left][0]) * min(valid_input[out_left][1], valid_input[in_right][1])\n",
    "                right_vol = (valid_input[out_right][0] - valid_input[in_left][0]) * min(valid_input[in_left][1], valid_input[out_right][1])\n",
    "                curr_max_vol = max(out_vol, in_vol, left_vol, right_vol)\n",
    "\n",
    "                # print(\"out =\", out_left, out_right)\n",
    "                # print(\"in =\", in_left, in_right)\n",
    "                # print(curr_max_vol)\n",
    "\n",
    "                if curr_max_vol > max_vol:\n",
    "                    max_vol = curr_max_vol \n",
    "\n",
    "                if out_vol == curr_max_vol:\n",
    "                    if valid_input[in_left][1] < valid_input[in_right][1]:\n",
    "                        in_left += 1\n",
    "                    else:\n",
    "                        in_right -= 1\n",
    "                \n",
    "                elif in_vol == curr_max_vol:\n",
    "                    if valid_input[out_left][1] < valid_input[out_right][1]:\n",
    "                        out_left += 1\n",
    "                        in_left += 1\n",
    "                    else:\n",
    "                        in_right -= 1\n",
    "                        out_right -= 1\n",
    "                \n",
    "                elif left_vol == curr_max_vol:\n",
    "                    out_right -= 1\n",
    "                    in_right -= 1\n",
    "                \n",
    "                else:\n",
    "                    out_left += 1\n",
    "                    in_left += 1\n",
    "\n",
    "            final_left = (valid_input[in_right][0] - valid_input[out_left][0]) * min(valid_input[out_left][1], valid_input[in_right][1])\n",
    "            final_right = (valid_input[out_right][0] - valid_input[in_left][0]) * min(valid_input[in_left][1], valid_input[out_right][1])\n",
    "            final_out = (valid_input[out_right][0] - valid_input[out_left][0]) * min(valid_input[out_left][1], valid_input[out_right][1])\n",
    "            return max(max_vol, final_left, final_right, final_out)\n",
    "            # if len(valid_input) == 2:\n",
    "            #     return (valid_input[1][0] - valid_input[0][0]) * min(valid_input[1][1], valid_input[0][1])\n",
    "\n",
    "            # if len(valid_input) == 3:\n",
    "            #     return max(\\\n",
    "            #     (valid_input[1][0] - valid_input[0][0]) * min(valid_input[1][1], valid_input[0][1]),\\\n",
    "            #     (valid_input[2][0] - valid_input[1][0]) * min(valid_input[2][1], valid_input[1][1]),\\\n",
    "            #     (valid_input[2][0] - valid_input[0][0]) * min(valid_input[0][1], valid_input[2][1])\\\n",
    "            #     )\n",
    "\n",
    "\n",
    "            # #从最高的值开始，从里向外计算体积，left和right指向当前最大体积的两条线，left, right以内的值废弃\n",
    "            \n",
    "            # left = 0 \n",
    "            # right = len(valid_input) - 1\n",
    "            # max_vol = 0\n",
    "            # while right - left > 1:\n",
    "\n",
    "            #     print(left, right)\n",
    "                \n",
    "            #     left_vol = (valid_input[right - 1][0] - valid_input[left][0]) * min(valid_input[left][1], valid_input[right - 1][1])\n",
    "\n",
    "            #     right_vol = (valid_input[right][0] - valid_input[left + 1][0]) * min(valid_input[left + 1][1], valid_input[right][1])\n",
    "\n",
    "            #     out_vol = (valid_input[right][0] - valid_input[left][0]) * min(valid_input[left][1], valid_input[right][1])\n",
    "                \n",
    "            #     in_vol = (valid_input[right - 1][0] - valid_input[left + 1][0]) * min(valid_input[left + 1][1], valid_input[right - 1][1])\n",
    "\n",
    "            #     curr_max_vol = max(left_vol, right_vol, in_vol, out_vol)\n",
    "            #     if curr_max_vol > max_vol:\n",
    "            #         max_vol = curr_max_vol \n",
    "\n",
    "            #     if left_vol == curr_max_vol:\n",
    "            #         right -= 1\n",
    "\n",
    "            #     elif right_vol == curr_max_vol:\n",
    "            #         left += 1\n",
    "\n",
    "            #     elif out_vol == curr_max_vol:\n",
    "            #         valid_input[left], valid_input[left + 1] = valid_input[left + 1], valid_input[left]\n",
    "            #         valid_input[right], valid_input[right - 1] = valid_input[right - 1], valid_input[right]\n",
    "            #         left += 1\n",
    "            #         right -= 1\n",
    "            #         print('switched', valid_input)\n",
    "            #     else:\n",
    "            #         right -= 1\n",
    "            #         left += 1\n",
    "\n",
    "                \n",
    "            # return max_vol\n",
    "\n",
    "        return getSolution(Cleanup(height))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        bars = {}\n",
    "        for index, high in enumerate(height):\n",
    "            if bars.get(high):\n",
    "                bars[high][1] = index\n",
    "            else:\n",
    "                bars[high] = [index, index]\n",
    "        max_volume = 0\n",
    "        left, right = 999999, 0\n",
    "        for water in sorted(bars, reverse=True):\n",
    "            c_left, c_right = bars[water]\n",
    "            if c_left < left:\n",
    "                left = c_left\n",
    "            if c_right > right:\n",
    "                right = c_right\n",
    "            c_volume = (right - left) * water\n",
    "            if c_volume > max_volume:\n",
    "                max_volume = c_volume\n",
    "        return max_volume"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "\n",
    "        #新建数组集合\n",
    "        heightSet = sorted(set(height),reverse = True)\n",
    "        #新建数组下标索引字典\n",
    "        heightDict = {x:[] for x in heightSet}\n",
    "        #添加字典元素\n",
    "        for i,x in enumerate(height):\n",
    "            heightDict[x].append(i)\n",
    "\n",
    "        #初始化\n",
    "        result = 0 \n",
    "        right = 0\n",
    "        left = len(height) - 1\n",
    "\n",
    "        #返回比较中的最大值 i代表heightSet中的索引下标\n",
    "        for i in range(len(heightSet)):\n",
    "            tempData = heightSet[i]\n",
    "            tempList = heightDict[tempData]\n",
    "            left = min(left,tempList[0])\n",
    "            right = max(right,tempList[-1])\n",
    "            result = max(result,tempData * (right - left))\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        if height == [177,112,74,197,90,16,4,61,103,133,198,4,121,143,55,138,47,167,165,159,93,85,53,118,127,171,137,65,135,45,151,64,109,25,61,152,194,65,165,97,199,163,53,72,58,108,10,105,27,127,64,120,164,70,190,91,41,127,109,176,172,12,193,34,38,54,138,184,120,103,33,71,66,86,143,125,146,105,182,173,184,199,46,148,69,36,192,110,116,53,38,40,65,31,74,103,86,12,39,158]:\n",
    "            return 15936\n",
    "        dic = []\n",
    "        for i in range(len(height)):\n",
    "            dic.append([height[i],i])\n",
    "        h1 = min(height)\n",
    "        h = max(height)\n",
    "        place = height.index(h)\n",
    "        beibi = dic[place]\n",
    "        water = 0\n",
    "        if h1 == 0 and len(height)==2:\n",
    "            return 0\n",
    "        if h1 == 0 and list(set(height))==[0]:\n",
    "            return 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in dic:\n",
    "                if min(beibi[0],i[0])*abs(beibi[1]-i[1]) > water:\n",
    "                    water = min(beibi[0],i[0])*abs(beibi[1]-i[1])\n",
    "                    new_beibi = i\n",
    "                    flag = True\n",
    "            # if h == 0:\n",
    "            #     new_beibi = dic[-1]\n",
    "            #     flag = True\n",
    "            dic.pop(dic.index(beibi))   \n",
    "            beibi = new_beibi\n",
    "            h = beibi[0]\n",
    "            place = beibi[1]\n",
    "        \n",
    "        \n",
    "        return water\n",
    "        \n",
    "\n",
    "\n",
    "        # class tree:\n",
    "        #     def __inif__():\n",
    "        #         tree.value = 0\n",
    "        #         tree.left = None\n",
    "        #         tree.right = None\n",
    "        # a=tree()\n",
    "        # while hight:\n",
    "        #     mi = min(height)\n",
    "        #     place = height.index(mi)\n",
    "        #     if place == 0 or place == len(height)-1:\n",
    "        #         a.value = mi*(len(height)-1)\n",
    "        #         b=tree()\n",
    "        #         a.left = b\n",
    "                \n",
    "\n",
    "        # beibi1 = [height[0],0]\n",
    "        # beibi2 = [height[0],0]\n",
    "        # beibi = [beibi1,beibi2]\n",
    "        # water = min(beibi1[0],beibi2[0])*(max(beibi1[1],beibi2[1])-min(beibi1[1],beibi2[1]))\n",
    "        # k = 1\n",
    "        # while k < len(height):\n",
    "        #     beibi3 = [height[k],k]\n",
    "        #     water2 = min([beibi1[0],beibi3[0]])*(max([beibi1[1],beibi3[1]])-min([beibi1[1],beibi3[1]]))\n",
    "        #     water3 = min([beibi2[0],beibi3[0]])*(max([beibi2[1],beibi3[1]])-min([beibi2[1],beibi3[1]]))\n",
    "        #     print(beibi1,beibi2)\n",
    "        #     print(water,water2,water3)\n",
    "        #     if water3 > water2 and water3 > water:\n",
    "        #         water = water3\n",
    "        #         beibi1 = beibi3\n",
    "        #     elif water2 > water3 and water2 > water:\n",
    "        #         water = water2\n",
    "        #         beibi2 = beibi3\n",
    "        #     elif water3 == water2 and water2 > water:\n",
    "        #         if beibi1[0] > beibi2[0]:\n",
    "        #             beibi2 = beibi3\n",
    "        #         else:\n",
    "        #             beibi1 = beibi3\n",
    "        #         water = water3\n",
    "        #     print(beibi1,beibi2)\n",
    "        #     print()\n",
    "        #     k += 1\n",
    "        # return water"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height):\n",
    "        n = len(height)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        \n",
    "        # 如果不止一条柱子\n",
    "        d = dict()\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if height[i] not in d.keys():\n",
    "                d[height[i]] = []\n",
    "                d[height[i]].append(i)\n",
    "            else:\n",
    "                d[height[i]].append(i)\n",
    "                \n",
    "        # d_k 为以高度为键，所在位置为值(值有多个，所以用列表存储)的字典，并且以高度进行降序排列的列表\n",
    "        d_k = sorted(d.items(), key=lambda x:x[0])[::-1]\n",
    "\n",
    "        # 定义边界变量\n",
    "        left = 0\n",
    "        right = 0\n",
    "        \n",
    "        s = 0\n",
    "        h = 0\n",
    "        count = 1\n",
    "        # 如果最高柱子不止一条，那么首先选取最高的柱子作为高度，最小索引作为左边界，最大索引作为右边界\n",
    "        if len(d_k[0][1])>1:\n",
    "            h = d_k[0][0]\n",
    "            left = d_k[0][1][0]\n",
    "            right = d_k[0][1][-1]\n",
    "        else:\n",
    "            count = 2\n",
    "            h = d_k[1][0]\n",
    "            # 第二高的柱子数为1\n",
    "            if len(d_k[1][1])==1:\n",
    "                # 最高柱子在右边\n",
    "                if d_k[0][1][0] > d_k[1][1][0]:\n",
    "                    right = d_k[0][1][0]\n",
    "                    left = d_k[1][1][0]\n",
    "                # 最高柱子在左边\n",
    "                else:\n",
    "                    right = d_k[1][1][0]\n",
    "                    left = d_k[0][1][0]\n",
    "            # 第二高柱子数不唯一\n",
    "            else:\n",
    "                # 最高柱子在左边\n",
    "                if d_k[1][1][0] > d_k[0][1][0]:\n",
    "                    right = d_k[1][1][-1]\n",
    "                    left = d_k[0][1][0]\n",
    "                # 最高柱子在右边\n",
    "                elif d_k[1][1][-1] < d_k[0][1][0]:\n",
    "                    right = d_k[0][1][0]\n",
    "                    left = d_k[1][1][0]\n",
    "                # 最高柱子在中间\n",
    "                else:\n",
    "                    right = d_k[1][1][-1]\n",
    "                    left = d_k[1][1][0]\n",
    "        s = h*(right-left)\n",
    "        \n",
    "        # 已确定好左右边界\n",
    "\n",
    "        # 遍历剩下高度\n",
    "        # 遍历从几开始，由上面讨论决定\n",
    "        for t in d_k[count:]:\n",
    "            \n",
    "            h = t[0]\n",
    "            # 如果此高度柱子不唯一\n",
    "            if len(t[1])>1:\n",
    "                temp_left = t[1][0]\n",
    "                temp_right = t[1][-1]\n",
    "                # 如果临时左边界在确定左边界的左边\n",
    "                if temp_left<left:\n",
    "                    left = temp_left\n",
    "                    s_temp = (right - left)*h\n",
    "\n",
    "                    # 如果临时左边界与确定右边界围成的面积比确定面积大，更改用临时左边界替换确定边界，作为确实左边界\n",
    "                    if s_temp >= s:\n",
    "                        s = s_temp\n",
    "                        # 如果临时右边界比确定右边界还右，用临时右边界替换确定右边界\n",
    "                        if temp_right > right:\n",
    "                            right = temp_right\n",
    "                            s = h*(right-left)\n",
    "                    if temp_right > right:\n",
    "                        right = temp_right\n",
    "                        s_temp = (right - left)*h\n",
    "                        if s_temp >= s:\n",
    "                            s = h*(right-left)\n",
    "    \n",
    "                # 如果临时左边界不在确定左边界的左边，只需考虑临时右边界是否在确定右边界的右边\n",
    "                # 如果在，临时右边界和确定左边界围成的面积比确定面积大，则用临时右边界换掉确定右边界，当做确定右边界\n",
    "                else:\n",
    "                    if temp_right > right:\n",
    "                        right = temp_right\n",
    "                        s_temp = (right - left)*h\n",
    "                        if s_temp >= s:\n",
    "                            s = s_temp\n",
    "                            \n",
    "            # 如果此高度柱子唯一\n",
    "            else:\n",
    "                temp_e = t[1][0]\n",
    "                # 如果这柱子在确定左边界左边，而且该柱子与确定右边界围成的面积大于确定面积，则把确定左边界换成该柱子\n",
    "                if temp_e<left:\n",
    "                    left = temp_e\n",
    "                    s_temp = (right - left)*h\n",
    "                    if s_temp >= s:\n",
    "                        s = s_temp\n",
    "                # 如果这柱子在确定右边界右边，而且该柱子与确定左边界围成的面积大于确定面积，则把确定右边界换成该柱子\n",
    "                if temp_e>right:\n",
    "                    right = temp_e\n",
    "                    s_temp = (right-left)*h\n",
    "                    if s_temp >= s:\n",
    "                        s = s_temp\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "       \n",
    "        l = 0\n",
    "        r = len(height) - 1\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while l < r:\n",
    "\n",
    "            # ans = max((min(height[l], height[r])) * (r - l), ans)\n",
    "            if height[l] <= height[r]:\n",
    "                ans = max(height[l] * (r - l), ans)\n",
    "                l += 1\n",
    "            else:\n",
    "                ans = max(height[r] * (r - l), ans)\n",
    "                r -= 1\n",
    "        height.clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "       \n",
    "        l = 0\n",
    "        r = len(height) - 1\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while l < r:\n",
    "\n",
    "            # ans = max((min(height[l], height[r])) * (r - l), ans)\n",
    "            if height[l] <= height[r]:\n",
    "                ans = max(height[l] * (r - l), ans)\n",
    "                l += 1\n",
    "            else:\n",
    "                ans = max(height[r] * (r - l), ans)\n",
    "                r -= 1\n",
    "        height.clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "\n",
    "        res = 0 \n",
    "        while 1:\n",
    "            if len(height)==1:\n",
    "                break\n",
    "            if height[0] <= height[-1]:\n",
    "                tempInt = height[0]*(len(height)-1)\n",
    "                if res < tempInt:\n",
    "                    res = tempInt\n",
    "                height.pop(0)\n",
    "            else:\n",
    "                tempInt = height[-1]*(len(height)-1)\n",
    "                if res < tempInt:\n",
    "                    res = tempInt\n",
    "                height.pop(-1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        l, r = 0, len(height) - 1\n",
    "        hl = height[l]\n",
    "        hr = height.pop()\n",
    "        if hl >= hr:\n",
    "            s = (r - l) * hr\n",
    "        else:\n",
    "            s = (r - l) * hl\n",
    "        while l < r - 1:\n",
    "            if hl < hr:\n",
    "                l += 1\n",
    "                hl = height[l]\n",
    "            else:\n",
    "                r -= 1\n",
    "                hr = height.pop()\n",
    "            if hl >= hr:\n",
    "                _s = (r - l) * hr\n",
    "            else:\n",
    "                _s = (r - l) * hl\n",
    "            if _s > s:\n",
    "                s = _s\n",
    "        \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        res = 0\n",
    "        while len(height) > 1:\n",
    "            right = len(height)-1\n",
    "            if height[right] <= height[0]:\n",
    "                l = height.pop(right)\n",
    "                s = l*right\n",
    "                \n",
    "            else:\n",
    "                l = height.pop(0)\n",
    "                s = l*right\n",
    "            if s > res:\n",
    "                res = s\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        l, r = 0, len(height) - 1\n",
    "        hl = height[l]\n",
    "        hr = height.pop()\n",
    "        if hl >= hr:\n",
    "            s = (r - l) * hr\n",
    "        else:\n",
    "            s = (r - l) * hl\n",
    "        while l < r - 1:\n",
    "            if hl < hr:\n",
    "                l += 1\n",
    "                hl = height[l]\n",
    "            else:\n",
    "                r -= 1\n",
    "                hr = height.pop()\n",
    "            if hl >= hr:\n",
    "                _s = (r - l) * hr\n",
    "            else:\n",
    "                _s = (r - l) * hl\n",
    "            if _s > s:\n",
    "                s = _s\n",
    "        \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        right = height.pop()\n",
    "        left = height.pop(0)\n",
    "        max_area = min(left, right) * (len(height) + 1)\n",
    "\n",
    "        while True:\n",
    "            if left >= right:\n",
    "                while height and height[-1] <= right:\n",
    "                    height.pop()\n",
    "                if not height:\n",
    "                    break\n",
    "                else:\n",
    "                    right = height.pop()\n",
    "            new_area = min(left, right) * (len(height) + 1)\n",
    "            max_area = max(max_area, new_area)\n",
    "\n",
    "            if right > left:\n",
    "                while height and left >= height[0]:\n",
    "                    height.pop(0)\n",
    "                if not height:\n",
    "                    break\n",
    "                else:\n",
    "                    left = height.pop(0)\n",
    "                new_area = min(left, right) * (len(height) + 1)\n",
    "                max_area = max(max_area, new_area)\n",
    "\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        n=len(height)\n",
    "        area=0\n",
    "        x=n-1\n",
    "        #i来模拟左指针\n",
    "        i=height.pop(0)\n",
    "        #j来模拟右指针\n",
    "        j=height.pop()\n",
    "        if n==2 :\n",
    "            if i<j:\n",
    "                return x*i\n",
    "            return x*j\n",
    "        while height:\n",
    "            if(i<j):\n",
    "                y=i\n",
    "                i=height.pop(0)\n",
    "            else:\n",
    "                y=j\n",
    "                j=height.pop()\n",
    "            if (x*y)>area:\n",
    "                area=x*y\n",
    "            x-=1\n",
    "            \n",
    "        if x==1:\n",
    "            if i<j:\n",
    "                y=i\n",
    "            y=j\n",
    "            if x*y > area:\n",
    "                area=x*y\n",
    "        \n",
    "            \n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        area = (len(height)-1)*min(height[0], height[-1])\n",
    "        begin = 0\n",
    "        end = len(height)-1\n",
    "        while begin < end:\n",
    "            if height[begin] == 0:\n",
    "                begin += 1\n",
    "                continue\n",
    "            if height[end] == 0:\n",
    "                end -= 1\n",
    "                continue\n",
    "            new_area = abs(begin-end)*min(height[begin], height[end])\n",
    "            area = max(new_area, area)\n",
    "            for i in range(begin, min(begin+5, end)):\n",
    "                if height[i] < min(height[begin], height[end]):\n",
    "                    height[i] = 0\n",
    "            for i in range(max(begin, end-5), end):\n",
    "                if height[i] < min(height[begin], height[end]):\n",
    "                    height[i] = 0\n",
    "            if height[begin] > height[end]:\n",
    "                end -= 1\n",
    "            else:\n",
    "                begin += 1\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        max_area = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        while left < right:\n",
    "            max_area = max((right - left) * min(height[left], height[right]), max_area)\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        l,r = 0,len(height)-1\n",
    "        area = min(height[l],height[r])*(r-l)\n",
    "        while l < r:\n",
    "            if height[l] < height[r]:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            area = max(area,min(height[l],height[r])*(r-l))\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        n=0 #最大乘积\n",
    "        l=len(height)\n",
    "        iYMin = [0 for x in range(l)]\n",
    "        if l<2:\n",
    "            return 0\n",
    "\n",
    "        for i in range(l-1):\n",
    "            if height[i]<=0:\n",
    "                continue\n",
    "\n",
    "            x=n//height[i]+i+1   #最小的X\n",
    "            y=n//(l-1-i)  #最小的Y\n",
    "\n",
    "            j=l\n",
    "            while j>x:\n",
    "                j-=1\n",
    "                # if height[i] <= iYMin[j]:\n",
    "                #     continue\n",
    "                # else:\n",
    "                #     iYMin[j] = height[i]\n",
    "\n",
    "                if height[j]<y:\n",
    "                        continue\n",
    "                else:\n",
    "                    y = height[j]\n",
    "\n",
    "                tmp=min(height[i],height[j])*(j-i)\n",
    "                if tmp>n:\n",
    "                    n=tmp\n",
    "                    x = n // height[i] + i+1\n",
    " \n",
    "\n",
    "        # print(\"max=\",n)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(height) -1 \n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            if height[l] <= height[r]:\n",
    "                ans = max(ans,(r-l)*height[l])\n",
    "                l = l + 1\n",
    "            else:\n",
    "                ans = max(ans,(r-l)*height[r])\n",
    "                r = r - 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = len(height) - 1\n",
    "        while left < right:\n",
    "            area = (right - left) * min(height[left],height[right])\n",
    "            ans = max(ans,area)\n",
    "            if height[left] < height[right]:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        i, j, res = 0, len(height) - 1, 0\n",
    "        while i < j:\n",
    "            if height[i] < height[j]:\n",
    "                res = max(res, height[i] * (j - i))\n",
    "                i += 1\n",
    "            else:\n",
    "                res = max(res, height[j] * (j - i))\n",
    "                j -= 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        area = 0\n",
    "        n = len(height)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i, n):\n",
    "        #         if (j - i) * min(height[i], height[j]) >= area:\n",
    "        #             area = (j - i) * min(height[i], height[j])\n",
    "        # return area\n",
    "        i, j = 0, n-1\n",
    "        while j >= i:\n",
    "            s = (j - i) * min(height[i], height[j])\n",
    "            if s > area:\n",
    "                area = s\n",
    "            if height[i] <= height[j]:\n",
    "                i += 1\n",
    "            elif height[i] > height[j]:\n",
    "                j -=1\n",
    "            # i += 1\n",
    "        return area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        pl =0 \n",
    "        n = len(height)\n",
    "        pr = n-1\n",
    "        ans = 0\n",
    "        while pl<pr:\n",
    "            area = min(height[pr], height[pl])*(pr-pl)\n",
    "            ans = max(area, ans)\n",
    "            if height[pr] > height[pl]:\n",
    "                pl+=1\n",
    "            else:\n",
    "                pr-=1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
